package leetcode;

/**
 * 60. 排列序列
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
 * <p>
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 * <p>
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 3, k = 3
 * 输出："213"
 * 示例 2：
 * <p>
 * 输入：n = 4, k = 9
 * 输出："2314"
 * 示例 3：
 * <p>
 * 输入：n = 3, k = 1
 * 输出："123"
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 9
 * 1 <= k <= n!
 */
public class GetPermutation {

    boolean[] used;
    int k1 = 0;
    String ans = "";

    /**
     * 求n的数的全部排列
     *
     * @param n
     * @param k
     * @return
     */
    public String getPermutation(int n, int k) {
        used = new boolean[n + 1];
        dfs(0, n, k, new StringBuilder());
        return ans;
    }

    public void dfs(int count, int n, int k, StringBuilder s) {
        if (count == n) {
            k1++;
            if (k1 == k) {
                ans = s.toString();
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            if (k1 == k) {
                return;
            }
            s.append(i);
            used[i] = true;
            dfs(count + 1, n, k, s);
            s.deleteCharAt(s.length() - 1);
            used[i] = false;
        }
    }
}
